import model.ListNode;

public class MergeKLists {
    //合并k个升序链表
    public ListNode code(ListNode[] lists) {
        return mergeSort(lists, 0, lists.length - 1);
    }

    public ListNode mergeSort(ListNode[] lists, int left, int right){
        if (left > right){
            return null;
        }

        if (left == right){
            return lists[left];
        }

        int mid = (left + right) / 2;
        ListNode l1 = mergeSort(lists, left, mid);
        ListNode l2 = mergeSort(lists, mid + 1, right);

        return mergeTwoList(l1, l2);
    }

    public ListNode mergeTwoList(ListNode cur1 ,ListNode cur2){
        if (cur1 == null){
            return cur2;
        }

        if (cur2 == null){
            return cur1;
        }

        ListNode newHead = new ListNode(0);
        ListNode prev = newHead;

        while (cur1 != null && cur2 != null){
            if (cur1.val < cur2.val){
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }else {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }


        if (cur2 != null){
            prev.next = cur2;
        }

        if (cur1 != null){
            prev.next = cur1;
        }

        return newHead.next;
    }
}
